package com.jack.leetcode.每日一题;

import java.util.Stack;

public class 从先序遍历还原二叉树 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static TreeNode recoverFromPreorder(String S) {
        Stack<TreeNode> stack = new Stack<>();
        int n = S.length();
        for(int i = 0;i < n;i++){
            int curLevel = 0;
            while(i < n && S.charAt(i) == '-'){
                i++;
                curLevel++;
            }
            int start = i;
            while(i < n && S.charAt(i) != '-'){
                i++;
            }
            TreeNode curNode = new TreeNode(Integer.valueOf(S.substring(start, i)));
            i--;
            if(stack.isEmpty()){
                stack.push(curNode);
                continue;
            }
            while(stack.size() > curLevel){
                stack.pop();
            }
            if(stack.peek().left != null){
                stack.peek().right = curNode;
            }else{
                stack.peek().left = curNode;
            }
            stack.push(curNode);
        }
        return stack.firstElement();
    }

    public static void main(String[] args) {
        recoverFromPreorder("1-2--3---4-5--6---7");
    }
}
